package UnionFind;

/**
 * @author chetaifu
 * 最终优化版本
 */
public class UnionFind {
    private int[] parent;

    /**
     * rank[i]表示以i为根的集合所表示的树的层数
     * */
    private int[] rank;
    private int size;

    public UnionFind(int n){
        this.size = n;
        parent = new int[n];
        rank = new int[n];
        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < n ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 把沿途的每个节点的父节点都设为根节点，减少h
     * O(h)复杂度
     */
    public int find(int p){
        assert (p >= 0 && p < size);
        return parent[p] == p ? p : (parent[p] = find(parent[p]));
    }

    /**
     * O(h)复杂度
     * */
    public boolean isConnected(int p, int q){
        return find(p) == find(q);
    }

    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度, h为树的高度
     */
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot){
            return;
        }

        if(rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
        } else if(rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        } else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            // 维护rank的值
            rank[qRoot] += 1;
        }
    }

}
